package main

var ansCount = 0
func findTargetSumWays(nums []int, target int) int {
	signs := make([]int, len(nums))
	ansCount = 0
	backtrack(nums, signs, target, 0)
	return ansCount
}

func backtrack(nums []int, signs []int, target int, index int) {
	if index == len(nums) {
		sum := 0
		for i, v := range nums {
			sum += signs[i] * v
		}
		if sum == target {
			ansCount++
		}
	} else {
		signs[index] = 1
		backtrack(nums, signs, target, index+1)
		signs[index] = -1
		backtrack(nums, signs, target, index+1)
	}
}

func main() {
	nums := []int{1,1,1,1,1}
	result := findTargetSumWays(nums, 3)
	println(result)
}